/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

#pragma once

template <typename Tv, typename Te> 
stack<Tv>* Graph<Tv, Te>::tSort(int s) { 
   reset(); int clock = 0; int v = s;
   stack<Tv>* S = new stack<Tv>; 
   do {
      if (UNDISCOVERED == status(v))
         if (!TSort(v, clock, S)) { 
            /*DSA*/print(S);
            while (!S->empty()) 
               S->pop(); break; 
         }
   } while (s != (v = (++v % n)));
   return S; 
}

template <typename Tv, typename Te> 
bool Graph<Tv, Te>::TSort(int v, int& clock, stack<Tv>* S) { 
   dTime(v) = ++clock; status(v) = DISCOVERED; 
   for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) 
      switch (status(u)) { 
         case UNDISCOVERED:
            parent(u) = v; status(v, u) = TREE;
            if (!TSort(u, clock, S)) 
               return false; 
            break;
         case DISCOVERED:
            status(v, u) = BACKWARD; 
            return false; 
         default: 
            status(v, u) = (dTime(v) < dTime(u)) ? FORWARD : CROSS;
            break;
      }
   status(v) = VISITED; S->push(vertex(v)); 
   return true; 
}
